/*
 * @Author: szx
 * @Date: 2021-12-23 14:17:16
 * @LastEditTime: 2021-12-23 16:32:42
 * @Description:
 * @FilePath: \leetcode\100-199\106\106.js
 */
function TreeNode(val, left, right) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
}
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
// var buildTree = function (inorder, postorder) {
//     const postLen = postorder.length;
//     if (postLen == 0) return null;
//     // 找到后序遍历的最后一个，即根节点
//     const root = new TreeNode(postorder[postLen - 1]);
//     // 叶子节点就返回
//     if (postorder.length == 1) return root;
//     // 在中序遍历里面找到这个根节点的位置，然后分成左右
//     const rootInIndex = inorder.indexOf(root.val);
//     const leftInArr = inorder.slice(0, rootInIndex);
//     const rightInArr = inorder.slice(rootInIndex + 1);
//     const leftInArrLen = leftInArr.length;
//     // 在后序遍历里面根据上述分好的左右数组大小来分后序遍历的左右数组
//     const leftPoArr = postorder.slice(0, leftInArrLen);
//     const rightPoArr = postorder.slice(leftInArrLen, postorder.length - 1);
//     root.left = buildTree(leftInArr, leftPoArr);
//     root.right = buildTree(rightInArr, rightPoArr);
//     return root;
// };

var buildTree = function(inorder, postorder) {
    if (!postorder.length) return null;
    const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
    let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
    const root = new TreeNode(rootVal); // 创建中间节点
    root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点
    root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点
    return root;
};
